#!/usr/bin/env python

'''
    Map Genearator Source Code
    Ripped from MUDServ to avoid writing a dungeon generator in Erlang for 7DRL 2011
'''

import sys
import json
import mutex
import math
from random import *
from ConfigParser import *
from time import sleep

__version__ = '0.1'
__author__ = 'Ian Wagner and Michael Chest'
__credits__ = ['Ian Wagner', 'Michael Chest', 'Dan Alexander',
               'Zak Richards', 'Reuben Deleon']
__license__ = 'BSD'
__status__ = 'Development'
__copyright__ = 'Copyright 2011 Demergo Studios'

# Symbolic constants for directions
NORTH = 0
EAST = 1
SOUTH = 2
WEST = 3

# Symbolic constants for feature tuple indices
X = 0
Y = 1
HEIGHT = 2
WIDTH = 3
TYPE = 4
CONNECTIONS = 5

# Symbolic constants for feature types
ROOM = 0
PASSAGE = 1
RANDOM = 2    # Used as arguments for addFeature

# Symbolic constants for exit direction
NONE = 0
UP = 1
DOWN = 2

DIR = 2   # for exit tuple access

DEBUG = True if '-d' in sys.argv else False

lock = mutex.mutex()    # Lock to make sure we don't generate duplicate boards or anything like that

class BoardGenerator:
  '''
    A class that... well... generates boards :)
  '''
  def __init__(self):
    self.board = [[' ' for i in range(80)] for i in range(24)]
    self.features = []         # List of tuples (x, y, height, width, type, [list of walls with features connected]) to keep track of features
    self.spawnX = 0
    self.spawnY = 0
    
    self.passageMaxLen = 6
    
  def generateRect(self, height, width):
    '''
      Generates a rectangle with a given size.
      
      The feature is returned as a 2-D list;
    '''
    rect = [['#' for i in range(width)] for i in range(height)]
    
    for i in range(1, height - 1):
      for j in range(1, width - 1):
        rect[i][j] = ' '
        
    return rect
    
  def addPassage(self, featureIndex, side, length):
    '''
      Adds a passage to the feature in the board (described by a feature tuple),
      on the specified side with given length.
    '''
    x = 0
    y = 0
    height = 0
    width = 0
    opening = (0, 0)
    feature = self.features[featureIndex]
    
    success = False
    fails = 0
    maxFails = 15
    
    # Attempt to add a passage
    while not success and fails < maxFails:
      if side == NORTH:
        # North extension
        x = randint(feature[X] + 1, feature[X] + feature[WIDTH] - 4)
        y = feature[Y] - length - 1
        height = length + 2
        width = 3
        opening = (x + 1, y + height - 1)
        connected = [SOUTH]
      elif side == EAST:
        # East extension
        x = feature[X] + feature[WIDTH] - 1
        y = randint(feature[Y] + 1, feature[Y] + feature[HEIGHT] - 4)
        height = 3
        width = length + 2
        opening = (x, y + 1)
        connected = [WEST]
      elif side == SOUTH:
        # South extension
        x = randint(feature[X] + 1, feature[X] + feature[WIDTH] - 4)
        y = feature[Y] + feature[HEIGHT] - 1
        height = length + 2
        width = 3
        opening = (x + 1, y)
        connected = [NORTH]
      elif side == WEST:
        # West extension
        x = feature[X] - length - 1
        y = randint(feature[Y] + 1, feature[Y] + feature[HEIGHT] - 4)
        height = 3
        width = length + 2
        opening = (x + length + 1, y + 1)
        connected = [EAST]
      
      success = self.canAddFeature(featureIndex, x, y, height, width)
      fails += 1
    if fails == maxFails:
      return False
      
    # Add the passage
    passage = self.generateRect(height, width)
    self.pasteIn(passage, x, y)
    self.board[opening[1]][opening[0]] = ' '
    self.features.append((x, y, height, width, PASSAGE, connected))
    self.features[featureIndex][CONNECTIONS].append(side)
    
    # Monsters
    if randint(0, 1) == 1:
      spawn = (x + (width / 2), y + (height / 2))
      self.board[spawn[1]][spawn[0]] = 'M'
    return True
    
  def canAddPassage(self, featureIndex, side, length):
    '''
      Checks if a passage can be added off of a room in board
    '''
    height = len(self.board)
    width = len(self.board[0])
    feature = self.features[featureIndex]
    
    if side in feature[CONNECTIONS] or feature[TYPE] != ROOM:
      return False
    elif side == NORTH:
      # North
      if feature[Y] - length - 2 <= 0 or feature[X] + 6 > feature[X] + feature[WIDTH]:
        return False
    elif side == EAST:
      # East
      if feature[X] + feature[WIDTH] + length + 2 >= width or feature[Y] + 5 > feature[Y] + feature[HEIGHT]:
        return False
    elif side == SOUTH:
      # South
      if feature[Y] + feature[HEIGHT] + length + 2 >= height or feature[X] + 5 > feature[X] + feature[WIDTH]:
        return False
    elif side == WEST:
      # West
      if feature[X] - length - 2 <= 0 or feature[Y] + 5 > feature[Y] + feature[HEIGHT]:
        return False
    else:
      return False
    
    return True
    
  def canAddFeature(self, featureIndex, x, y, height, width):
    '''
      Checks if a room can be added off another feature (must be a passage)
    '''
    feature = self.features[featureIndex]
    
    if ((x + width + 2 >= len(self.board[0])) or (y + height + 2 >= len(self.board)) or (x < 0) or (y < 0)):
      return False
    
    # Check to make sure we aren't overwriting anything
    try:
      for i in range(1, height + 1):
        for j in range(1, width + 1):
          if self.board[i + y][j + x] != ' ':
            return False
    except:
      return False
    
    return True
    
  def addRoom(self, featureIndex):
    '''
      Adds a room to the passage described in self.features[featureIndex]
    '''
    maxFails = 20             # Max fails to add a feature to the map before giving up
    feature = self.features[featureIndex]
    
    if feature[TYPE] != PASSAGE:
      return False
    
    minX = 0
    maxX = 0
    minY = 0
    maxY = 0
    
    # * Determine the minimum and maximum ranges for (x, y) of the top-left
    #   corner of the room
    # * Determine the formulas for minimum and maximum height based on those values
    # * Determine which connections will be added
    # * Determine which tile to knock out for the opening
    if feature[CONNECTIONS] == [SOUTH]:
      # Attach south of room to north of passage
      minX = feature[X] - 10
      maxX = feature[X] - 5
      minY = feature[Y] - 10
      maxY = feature[Y] - 5
      minHeight = 'feature[Y] - y + 1'
      maxHeight = minHeight
      minWidth = 'abs(feature[X] - x) + 5'
      maxWidth = 'abs(feature[X] - x) + 15'
      passageConn = NORTH
      roomConn = SOUTH
      opening = (feature[X] + 1, feature[Y])
    elif feature[CONNECTIONS] == [NORTH]:
      # Attach north of the room to south of passage
      minX = feature[X] - 10
      maxX = feature[X] - 5
      minY = feature[Y] + feature[HEIGHT] - 1
      maxY = feature[Y] + feature[HEIGHT] - 1
      minHeight = '5'
      maxHeight = '10'
      minWidth = 'abs(feature[X] - x) + 5'
      maxWidth = 'abs(feature[X] - x) + 15'
      passageConn = SOUTH
      roomConn = NORTH
      opening = (feature[X] + 1, feature[Y] + feature[HEIGHT] - 1)
    elif feature[CONNECTIONS] == [WEST]:
      # Attach west of room to east of passage
      minX = feature[X] + feature[WIDTH] - 1
      maxX = feature[X] + feature[WIDTH] - 1
      minY = feature[Y] - 10
      maxY = feature[Y] - 5
      minHeight = 'abs(feature[Y] - y) + 5'
      maxHeight = 'abs(feature[Y] - y) + 10'
      minWidth = '5'
      maxWidth = '15'
      passageConn = EAST
      roomConn = WEST
      opening = (feature[X] + feature[WIDTH] -1, feature[Y] + 1)
    elif feature[CONNECTIONS] == [EAST]:
      # Attach east of room to west of passage
      minX = feature[X] - 10
      maxX = feature[X] - 5
      minY = feature[Y] - 10
      maxY = feature[Y] - 5
      minHeight = 'abs(feature[Y] - y) + 5'
      maxHeight = 'abs(feature[Y] - y) + 10'
      minWidth = 'feature[X] - x + 1'
      maxWidth = minWidth
      passageConn = WEST
      roomConn = EAST
      opening = (feature[X], feature[Y] + 1)
    else:
      return False
    
    if minX < 0 or minY < 0:
      return False
    
    # Generate the (x, y) coordinate for the top-left corner, height, and width
    x = randint(minX, maxX)
    y = randint(minY, maxY)
    height = randint(eval(minHeight), eval(maxHeight))
    width = randint(eval(minWidth), eval(maxWidth))
    
    # Make sure that it is ok to put the room there, and if not re-compute
    fails = 0
    while not self.canAddFeature(featureIndex, x, y, height, width) and fails < maxFails * 3:
      x = randint(minX, maxX)
      y = randint(minY, maxY)
      height = randint(eval(minHeight), eval(maxHeight))
      width = randint(eval(minWidth), eval(maxWidth))
      fails += 1
      
    if fails == maxFails * 3:
      return False
      
    # Finally, we are clear to add the room to the map
    self.features.append((x, y, height, width, ROOM, [roomConn]))
    self.features[featureIndex][CONNECTIONS].append(passageConn)
    room = self.generateRect(height, width)
    self.pasteIn(room, x, y)
    self.board[opening[1]][opening[0]] = ' '
    
    # Monsters
    if randint(0, 1) == 1:
      spawn = (x + (width / 2), y + (height / 2))
      self.board[spawn[1]][spawn[0]] = 'M'
    return True
    
  def overlaps(self, x, y, height, width):
    '''
      Checks if one feature starting at (x, y) with height and width will overlap
      existing features
    '''
    for i in range(height):
      for j in range(width):
        try:
          if self.board[i + y][j + x] == '#':
            return True
        except:
          return True
        
    return False
    
  def pasteIn(self, src, x, y):
    '''
      "Paints" the contents of src on top of self.board starting at (x, y) and
      decreasing down and to the right.
      
      src is a 2-D list.
    '''
    error = ''
    for i in range(len(src)):
      for j in range(len(src[0])):
        try:
          self.board[i + y][j + x] = src[i][j]
        except IndexError:
          error += 'i: %d j: %d i+y: %d j+x: %d\n' % (i, j, i + y, j + x)
          pass
    if (error):
      print error
    
  def addRandomFeature(self, type=RANDOM):
    maxFails = 20             # Max fails to add a feature to the map before giving up
    
    if type == RANDOM:
      type = randint(0, 1)    # Decide what type of feature to add
    
    side = randint(0, 3)
    featureIndex = randint(0, len(self.features) - 1)
    fails = 0
    
    if type == PASSAGE:
      # Add a passage
      length = randint(3, 8)
      
      while not self.canAddPassage(featureIndex, side, length) and fails < maxFails:
        length = randint(3, 8)
        side = randint(0, 3)
        fails += 1
      if fails == maxFails:
        return False
      
      return self.addPassage(featureIndex, side, length)
    elif type == ROOM:
      # Add a room
      
      # Check that the type of feature is a passage with only one existing connection
      while (((self.features[featureIndex][TYPE] != PASSAGE) or (len(self.features[featureIndex][CONNECTIONS]) != 1)) and (fails < maxFails)):
        featureIndex = randint(0, len(self.features) - 1)
        fails += 1
      if fails == maxFails:
        return False
      
      self.addRoom(featureIndex)
    
  def addExit(self, exit):
    '''
      Adds an exit described by the exit tuple in the form (X, Y, DIR) to the
      map
    '''
    x = 0
    y = 0
    opening = (0, 0)
    
    if exit[DIR] == UP:
      self.board[Y][X] = 'U'
    elif exit[DIR] == DOWN:
      self.board[Y][X] = 'D'
    else:
      if exit[Y] == 0:
        # Start at north end of board
        x = exit[X] - 1
        y = exit[Y]
        height = 3
        width = 3
        
        try:
          while not self.overlaps(x, y, height, width):
            height += 1
          
          if self.board[y + height - 1][x] != '#' or self.board[y + height - 1][x + 1] != '#' or self.board[y + height - 1][x + 2] != '#':
            return False
        except:
          return False
        
        openings = [(exit[X], exit[Y]), (exit[X], exit[Y] + height - 1)]
        
      elif exit[Y] == len(self.board) - 1:
        # Start at south end of board
        x = exit[X] - 1
        y = exit[Y] - 2
        height = 3
        width = 3
        
        try:
          while not self.overlaps(x, y, height, width):
            y -= 1
            height += 1
            
          if self.board[y][x] != '#' or self.board[y][x + 1] != '#' or self.board[y][x + 2] != '#':
            return False
        except:
          return False
          
        openings = [(exit[X], exit[Y]), (exit[X], y)]
        
      elif exit[X] == 0:
        # Start at west end of board
        x = exit[X]
        y = exit[Y] - 1
        height = 3
        width = 3
        
        try:
          while not self.overlaps(x, y, height, width):
            width += 1
          
          if self.board[y][x + width - 1] != '#' or self.board[y + 1][x + width - 1] != '#' or self.board[y + 2][x + width - 1] != '#':
            return False
        except:
          return False
        
        openings = [(exit[X], exit[Y]), (exit[X] + width - 1, exit[Y])]
        
      elif exit[X] == len(self.board[0]) - 1:
        # Start at east end of board
        x = exit[X] - 3
        y = exit[Y] - 1
        height = 3
        width = 3
        
        try:
          while not self.overlaps(x, y, height, width):
            x -= 1
            width += 1
          
          if self.board[y][x] != '#' or self.board[y + 1][x] != '#' or self.board[y + 2][x] != '#':
            return False
        except:
          return False
          
        openings = [(exit[X] - width, exit[Y]), (exit[X]  - 1, exit[Y])]
      
      passage = self.generateRect(height, width)
      self.pasteIn(passage, x, y)
      try:
        for opening in openings:
          self.board[opening[Y]][opening[X]] = '+'
      except:
        pass
      return True
    
  def generateBoard(self, spawnX, spawnY, height, width, exits=[]):
    '''
      Generates a random board in teh roguelike style
      
      spawnX and spawnY - x and y dimensions of main spawn coordinate
      height and width - height and width of the board area
      exits - a list of tuples in the form (X, Y, DIR) specifying an entrance/exit
        location's coordinates and direction. Possible values for DIR are defined
        by the constants NONE, UP, DOWN (0, 1, 2)
    '''
    self.features = []      # List of tuples (x, y, height, width) to keep track of features
    
    while len(self.features) < 15:
      self.board = [[' ' for i in range(width)] for i in range(height)]
      self.features = []      # List of tuples (x, y, height, width) to keep track of features
      self.spawnX = spawnX
      self.spawnY = spawnY
      
      if spawnX >= width - 5 or spawnX <= 5 or spawnY >= height - 5 or spawnY <= 5:
        return self.board
      
      # Create the start feature
      x = randint(spawnX - 5, spawnX - 2)
      y = randint(spawnY - 4, spawnY - 1)
      featureHeight = randint(6, min(10, height - y - 1))
      featureWidth = randint(6, min(10, width - x - 1))
      self.features.append((x, y, featureHeight, featureWidth, ROOM, []))
      
      startfeature = self.generateRect(featureHeight, featureWidth)
      self.pasteIn(startfeature, x, y)
      
      self.board[spawnY][spawnX] = 'S';
      
      # Add some passages
      self.addRandomFeature(PASSAGE)
      self.addRandomFeature(PASSAGE)
      self.addRandomFeature(ROOM)
      
      # Randomly add a reasonable amount of features
      nLoops = 3
      
      for i in range(nLoops):
        fails = 0
        maxFails = 25
        while fails < maxFails:
          success = self.addRandomFeature()
          if not success:
            fails += 1
        
        # Attempt to add rooms onto the end of passages
        for featureIndex in range(len(self.features)):
          self.addRoom(featureIndex)
      
        # Attempt to add rooms onto the end of passages (one last time lol)
        for featureIndex in range(len(self.features)):
          self.addRoom(featureIndex)
          
      # Add in the exits
      #for exit in exits:
      #  if not self.addExit(exit):
      #    self.features = []    # Force map re-build
    return self.board
    
  def getJSONBoard(self):
    '''
      Returns the JSON stringified representation of self.board
    '''
    board = {}
    
    # Set dungeon parameters
    board['height'] = len(self.board)
    board['width'] = len(self.board[0])
    board['monsters'] = []
    board['spawn'] = {}
    
    # Build the "map"
    for i in range (len(self.board)):
      for j in range(len(self.board[0])):
        if self.board[i][j] != ' ':
          if not board.has_key(str(i)):
            board[str(i)] = {}
          c = self.board[i][j]
          if c in 'SUD+':    # if c is S, U, or D (spawn, up, down)
            spawnPoint = {'x': j, 'y': i}
            
            # Determine which spawn point this is
            if c == 'U':
              point = 'up'
            elif c == 'D':
              point = 'down'
            elif i == 0:
              point = 'north'
            elif i == len(self.board) - 1:
              point = 'south'
            elif j == 0:
              point = 'west'
            elif j == len(self.board[0]) - 2:
              point = 'east'
            elif c == 'S':
              point = 'main'
            else:
              board[str(i)][str(j)] = {'ascii': c}
              continue
            
            board['spawn'][point] = spawnPoint
            if c != 'S':
              board[str(i)][str(j)] = {'ascii': '+'}
          elif c == 'M':
            board['monsters'].append((j, i))
          else:
            board[str(i)][str(j)] = {'ascii': c}
    
    return json.dumps(board)

class WorldMap:
  '''
    WorldMap for MUDServ
    
    This class will keep track of fetching and creating maps in the database
  '''
  def __init__(self):
    # Types of zones that are defined by the server. The client can render however
    # it desires
    self.zones = ['dungeon', 'overworld', 'forest']
    self.boardGen = BoardGenerator()
    
    self.boardHeight = 50
    self.boardWidth = 90
    
  def fetchBoard(self, x, y, z, canGenerate=True):
    '''
      Fetches the board located at point (x, y, z) in the game world.
      If canGenerate is True, a nonexistent board will be generated when
      requested.
    '''
    result = Board.query.filter_by(x=x).filter_by(y=y).filter_by(z=z).first()
    if not result and canGenerate:
      result = self.generateBoard(x, y, z, self.boardHeight, self.boardWidth)
    result = Board.query.filter_by(x=x).filter_by(y=y).filter_by(z=z).first()
    return result
    
  def generateBoard(self, x, y, z, height, width):
    '''
      Generates a board for position x, y, and z in the world space. Returns
      the model.Board object representing the newly created board.
    '''
    while not lock.testandset():
      sleep(0.1)
    # Make sure we don't already have a board here
    result = Board.query.filter_by(x=x).filter_by(y=y).filter_by(z=z).first()
    if result:
      lock.unlock()
      return result
    
    # Check where we need maps to link
    exits = []
    
    # Check North
    result = Board.query.filter_by(x=x).filter_by(y=y+1).filter_by(z=z).first()
    if result and json.loads(result.data).get('spawn', {}).get('south', {}).get('x', None):
      exits.append((json.loads(result.data).get('spawn').get('south').get('x'), 0, NONE))
    else:
      exits.append((randint(5, self.boardWidth - 5), 0, NONE))
      
    # Check South
    result = Board.query.filter_by(x=x).filter_by(y=y-1).filter_by(z=z).first()
    if result and json.loads(result.data).get('spawn', {}).get('north', {}).get('x', None):
      exits.append((json.loads(result.data).get('spawn').get('north').get('x'), self.boardHeight - 1, NONE))
    else:
      exits.append((randint(5, self.boardWidth - 5), self.boardHeight - 1, NONE))
      
    # Check East
    result = Board.query.filter_by(x=x+1).filter_by(y=y).filter_by(z=z).first()
    if result and json.loads(result.data).get('spawn', {}).get('west', {}).get('y', None):
      exits.append((self.boardWidth - 1, json.loads(result.data).get('spawn').get('west').get('y'), NONE))
    else:
      exits.append((self.boardWidth - 1, randint(5, self.boardHeight - 5), NONE))
    
    # Check West
    result = Board.query.filter_by(x=x-1).filter_by(y=y).filter_by(z=z).first()
    if result and json.loads(result.data).get('spawn', {}).get('east', {}).get('y', None):
      exits.append((0, json.loads(result.data).get('spawn').get('east').get('y'), NONE))
    else:
      exits.append((0, randint(5, height - 5), NONE))
      
    # Random note: spawning at (10, 10) seems to generate relatively good maps
    # efficiently as opposed to starting somewhere in the middle of the board
    # and trying to work outward since the generation is random
    gen = BoardGenerator()
    gen.generateBoard(10, 10, height, width, exits)
    
    board = Board(x=x, y=y, z=z, data=unicode(gen.getJSONBoard()), name=unicode('board (%d, %d, %d)' % (x, y, z)))
    session.commit()
    lock.unlock()
    return board
    
# Print out a random map and its JSON representation if this script is run by itself
if __name__ == '__main__':
  height = 50
  width = 90
  gen = BoardGenerator()
  #exits = [(0, randint(5, height - 5), NONE), (randint(5, width - 5), 0, NONE), (width - 1, randint(5, height - 5), NONE), (randint(5, width - 5), height - 1, NONE)]
  board = '\n'.join([''.join(c) for c in gen.generateBoard(10, 10, height, width, exits=[])])
  sys.stdout.write(gen.getJSONBoard())
  sys.stdout.flush()
  if DEBUG:
    print board